import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution39 {

    public static void main(String args[]) {
        Solution39 s = new Solution39();
        System.out.println(s.combinationSum(new int[]{2, 2, 2}, 6));
    }

    HashMap<List<Integer>, Integer> mp;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        mp = new HashMap<>();
        Arrays.sort(candidates);
        return dfs(candidates, 0, target);
    }

    public List<List<Integer>> dfs(int[] nums, int st, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        if(target == 0){
            ret.add(new ArrayList<>());
            return ret;
        }
        if(st == nums.length){
            return ret;
        }
        for (int i = 0; nums[st] * i <= target; i++) {
            List<Integer> cl = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                cl.add(nums[st]);
            }
            List<List<Integer>> rl = dfs(nums, st + 1, target - nums[st] * i);
            for (int j = 0; j < rl.size(); j++) {
                List<Integer> tl = new ArrayList<>(cl);
                tl.addAll(rl.get(j));
                if (!mp.containsKey(tl)) {
                    ret.add(tl);
//                    mp.put(tl, 1);
                }
            }
        }
        return ret;
    }
}
